package java0328;

import java.util.Arrays;
import java.util.Stack;

public class MySort {

    public static void insertSort(int[] arr) {
        int bound = 1;
        // [0,bound) 是已排序序列
        for (; bound < arr.length; bound++) {
            int cur = bound - 1;
            int v = arr[bound];
            for (; cur >= 0; cur--) {
                if (arr[cur] > v) {
                    arr[cur + 1] = arr[cur];
                }else {
                    break;
                }
            }
            arr[cur + 1] = v;
        }
    }

    public static void shellSort(int[] arr) {
        int gap = arr.length / 2;
        for (; gap >= 1; gap /= 2) {
            _shellSort(arr, gap);
        }
    }

    private static void _shellSort(int[] arr, int gap) {
        int bound = gap;
        for (; bound < arr.length; bound++) {
            int cur = bound - gap;
            int v = arr[bound];
            for (; cur >= 0; cur -= gap) {
                if (arr[cur] > v) {
                    arr[cur + gap] = arr[cur];
                }else {
                    break;
                }
            }
            arr[cur + gap] = v;
        }
    }

    public static void selectSort(int[] arr) {
        int bound = 0;
        for (; bound < arr.length; bound++) {
            for (int cur = bound + 1; cur < arr.length; cur++) {
                if (arr[bound] > arr[cur]) {
                    swap(arr, bound, cur);
                }
            }
        }
    }

    private static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }

    public static void heapSort(int[] arr) {
        createHeap(arr);
        int size = arr.length;
        for (int index = arr.length - 1; index >= 0; index--) {
            swap(arr, 0,index);
            size--;
            shiftDown(arr, size, 0);
        }
    }

    private static void createHeap(int[] arr) {
        int index = (arr.length - 1 - 1) / 2;
        for (; index >= 0; index--) {
            shiftDown(arr, arr.length, index);
        }
    }

    private static void shiftDown(int[] arr, int size, int index) {
        int parent = index;
        int child = index * 2 + 1;
        while (child < size) {
            if(child + 1 < size && arr[child + 1] > arr[child]) {
                child++;
            }
            if (arr[parent] < arr[child]) {
                swap(arr, parent, child);
            }else {
                break;
            }
            parent = child;
            child = 2 * parent + 1;
        }
    }

    public static void bubbleSort(int[] arr) {
        int bound = 0;
        for (; bound < arr.length; bound++) {
            for (int index = arr.length - 1; index - 1 >= 0; index--) {
                if (arr[index - 1] > arr[index]) {
                    swap(arr, index - 1, index);
                }
            }
        }
    }

    public static void quickSort(int[] arr) {
        _quickSort(arr, 0, arr.length - 1);
    }

    private static void _quickSort(int[] arr, int left, int right) {
        if (left - right >= 0) {
            return;
        }
        int index = partition(arr, left, right);
        _quickSort(arr, left, index - 1);
        _quickSort(arr, index + 1,right);
    }

    private static int partition(int[] arr, int left, int right) {
        int l = left;
        int r = right;
        int v = arr[right];
        while (l < r) {
            while (l < r && arr[l] < v) {
                l++;
            }
            while (l < r && arr[r] >= v) {
                r--;
            }
            swap(arr, l, r);
        }
        swap(arr, l, right);
        return l;
    }

    // 非规划写法快速排序
    public static void quickSortByLoop(int[] arr) {
        // 利用栈的特性
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        stack.push(arr.length - 1);
        while (stack.isEmpty() == false) {
            int right = stack.pop();
            int left = stack.pop();
            if (right <= left) {
                continue;
            }
            int index = partition(arr, left, right);
            stack.push(left);
            stack.push(index - 1);
            stack.push(index + 1);
            stack.push(right);
        }
    }

    public static void mergeSort(int[] arr) {
        _mergeSort(arr, 0, arr.length);
    }

    private static void _mergeSort(int[] arr, int begin, int end) {
        if (end - begin <= 1) {
            return;
        }
        int mid = (begin + end) / 2;
        _mergeSort(arr, begin, mid);
        _mergeSort(arr, mid, end);
        merge(arr, begin, mid, end);
    }

    private static void merge(int[] arr, int begin, int mid, int end) {
        if (end - begin <= 1) {
            return;
        }
        int[] tmp = new int[end - begin];
        int index1 = begin;
        int index2 = mid;
        int cur = 0;
        while (!(index1 >= mid || index2 >= end)) {
            if (arr[index1] <= arr[index2]) {
                tmp[cur] = arr[index1];
                cur++;
                index1++;
            }else {
                tmp[cur] = arr[index2];
                cur++;
                index2++;
            }
        }
        while (index1 < mid) {
            tmp[cur] = arr[index1];
            cur++;
            index1++;
        }
        while (index2 < end) {
            tmp[cur] = arr[index2];
            cur++;
            index2++;
        }
        for (int i = 0; i < tmp.length; i++) {
            arr[begin + i] = tmp[i];
        }
    }

    public static void mergeSortByLoop(int[] arr) {
        int gap = 1;
        for (; gap < arr.length; gap *= 2) {
            for (int i = 0; i < arr.length; i += gap * 2) {
                int left = i;
                int mid = i + gap;
                if (mid >= arr.length) {
                    mid = arr.length;
                }
                int right = i + gap + gap;
                if (right >= arr.length) {
                    right = arr.length;
                }
                merge(arr, left, mid, right);
            }
        }
    }


    public static void main(String[] args) {
        int[] arr = {9,5,2,7,4,5,6,8,7,4,5,1};
//        insertSort(arr);
//        shellSort(arr);
//        selectSort(arr);
//        heapSort(arr);
//        bubbleSort(arr);
//        quickSort(arr);
//        quickSortByLoop(arr);
//        mergeSort(arr);
        mergeSortByLoop(arr);
        System.out.println(Arrays.toString(arr));
    }
}
